Flow control mechanisms in computer networks govern the transfer of packets from a source node to a destination node. Typical flow control mechanisms include negative-acknowledgment (NACK)/retry, drop/source-timeout/retry, credit/debit, and network buffering. Generally, a source node sends a packet to a destination node, where the destination node has a finite amount of “ingress buffering” for holding packets it has received from the source node prior to processing.
In NACK/retry flow control mechanisms, if the packet reaches the destination node and the destination node has no buffering available for the incoming packet, the packet is dropped and a NACK message is sent from the destination node back to the source node. The source node will then retry sending the packet at a later time.
However, a drawback of NACK/retry is that the source node must provide buffering for a sent packet because, until the source node receives an ACK (acknowledgment) or a NACK message, the source node does not know whether the destination node has a buffer available for holding the packet. Otherwise, if the destination node drops the packet and the source node has not preserved the packet in its own buffer, the packet is lost.
A larger drawback is the complexity introduced by the “retry” flow at the source node to resend the NACK'ed packets.
Still another drawback is that any design using NACK/retry must ensure that the NACK message is able to progress through the network back to the source node, even when the network is congested with sent packets. Additionally, the NACK message itself consumes valuable bandwidth that could be otherwise used for packets.
The drop/source-timeout/retry flow mechanism is similar to NACK/retry. The sent packet can be dropped and a response sent back to the source node when the destination node has no buffering. Additionally, in drop/source-timeout/retry, the sent packet can be dropped whenever there is too much network congestion. The source node will automatically retry sending a packet if the source node has not received a response from the destination node after some fixed time interval or timeout.
In addition to the drawbacks of NACK/retry, drop/source-timeout/retry has drawbacks regarding its timeout. The timeout may be either too long or too short. If the timeout is too long, when the destination node drops packets, the destination node must wait too long to receive a resent packet, thereby increasing system latency. On the other hand, if the timeout is too short, the likelihood of the source node unnecessarily sending the packet twice increases. As such, the system has to be able to cope with two (or more) instances of the same packet, resulting in increased complexity and hardware cost, as well as increased congestion.
In credit/debit flow mechanisms, the source node keeps track of the number of buffers available at the destination node through the use of “credits” and “debits.” A source node will only send a packet to a destination node if the source node knows there is a free buffer available at the destination node to accept the packet. When the source node sends a packet to the destination node, the source node “debits” (decrements) a local count of the number of free buffers the destination node has available. When the destination node removes a packet from its incoming buffers, the destination node sends a “credit” message back to the source node, and the source node “credits” (increments) the local count of the number of free buffers the destination node has available.
The credit/debit mechanism requires a fixed partitioning of the destination node's incoming buffers among the n source nodes. If the destination node has a total of B incoming buffers, it may allocate B/n buffer entries to each source node. This works well if traffic to the destination node from all the source nodes is exactly uniform. But any deviation from uniform traffic will cause inefficiencies in the utilization of the B buffers. A degenerate form of this design is to provide enough buffering at every destination node for all possible packets. In other words, if each of the n source nodes can have P packets in-flight, then each destination node must have P*n buffer entries. The drawback with this mechanism is that it leads to an inefficient, area-hungry design because the buffer utilization is usually very low.
In a network buffering flow mechanism, the network itself provides buffering for packets that can not be accepted at the destination node. The network allows packets to “stall” in the network, causing packets traveling on the network behind a stalled packet to be blocked by the stalled packet. Alternatively, special route-around logic and buffering can be used to allow packets behind the stalled packet to route past the stalled packet.
While this type of design may be effective for certain topologies, it prevents packet delivery in others, e.g., ring topologies. In a ring topology, since the packets travel a circular route, stalling can completely block delivery of packets behind the stalled packet unless complex and hardware intensive route-around schemes are employed.
Accordingly, there is a need in the art to overcome the drawbacks of typical flow control mechanisms for packet transport, particularly in ring topologies.